COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	CS306     MIDTERM EXAMINATION                           FALL 1985
C00008 ENDMK
C⊗;
CS306     MIDTERM EXAMINATION                           FALL 1985

	This examination is open book and notes.
Write LISP functions as follows except where something else is
requested.  Either notation may be used.


1. [20 points] structures[n]  is a list of all structures of S-expressions with
n  atoms using only the atom  A.  Thus

structures[4] = ((A . (A . (A. A))) (A . ((A . A) . A)) ((A . A) . (A . A))
((A . (A . A)) . A) (((A . A) . A) . A))


2. [25 points] Consider conditional expressions  (if p a b), where any of
p,  a  and  b  may be conditional expressions.  If any  p  is  T  or  F, 
the expression may be simplified.  Moreover, any occurrence of  p  in
a  may be replaced by  T  and any occurrence of  p  in  b  may be
replaced by  F.  ifsimp[exp]  is the result of applying these
simplifications to  exp  and its subexpressions until they can no
longer be applied.


3. [20 points] Define

	length u ← if n u then 0 else 1 + length d u,

and as usual

	u*v ← if n u then v else a u . [d u * v].

Prove that

	∀u v.(length[u*v] = length u + length v).

In the proof you may use any facts you like about the properties of addition,
but you must state what facts you are using.  Be sure and state the
hypothesis on which you are doing induction.


4. [35 points] remove[x,u]  returns the list  u
with all top-level occurrences of  x  removed.  This is similar to
the Common Lisp function   DELETE, but  DELETE  destructively
modifies  u  which your function shouldn't do   For example,
remove[A, (A (B C) A D)] =  ((B C) D),
remove[(B C), (A (B C) A D)] =  (A A D),
remove[E, (A (B C) A D)] =  (A (B C) A D).

a.  [10 points] Write the function  remove.
Now use induction to prove that

   ∀x u.member[x,remove[x,u]] = NIL.  

b.  [10 points] Identify the induction principle used and write
the formula   phi  used in the induction.

c.  [15 points] Prove the basis and the inductive steps, thus
completing the proof by induction.